package com.ljx.DijkStra;

/**
 * @author 李加喜
 * @Package com.ljx.DijkStra
 * @date 2021-11-10 21:30
 */

import java.util.*;

/**
 *  网络延迟时间
 */
public class InternetYanChi {
    public static void main(String[] args) {

    }
    public int networkDelayTime(int[][] times, int n, int k) {
        // 节点编号是从1开始的  所以要一个大小为n+1的领接表
        LinkedList[] graph= new LinkedList[n+1];
        for (int i=1;i<=n;i++){
            graph[i]=new LinkedList();
        }
        // 构造图
        for (int[] edge:times){
            int from=edge[0];
            int to=edge[1];
            int width=edge[2];
            // 邻接表存储图结构  同时存储权重信息
            graph[from].add(new int[]{to,width});
        }
        // 调用 dijkstra算法计算以节点k为起点到其他节点的最短路径
        int[] distTo=dijkstra(k,graph);
        int res=0;
        for (int i = 1; i < distTo.length; i++) {
            if (distTo[i] == Integer.MAX_VALUE) {
                // 有节点不可达，返回 -1
                return -1;
            }
            res = Math.max(res, distTo[i]);
        }
        return res;
    }
    class State{
        // 图的节点
        int id;
        // 从start节点到当前节点的距离
        int distFromStart;
        State (int id,int distFromStart){
            this.id=id;
            this.distFromStart=distFromStart;
        }
    }
    // 输入一个起点start 计算从start到其他节点的最短距离
    int[] dijkstra(int start ,List<int[]>[] graph){
        // 定义distTo[i]就是start到当前节点i的最短距离
        int[] distTo=new int[graph.length];
        Arrays.fill(distTo,Integer.MAX_VALUE);
        // 最短距离是0
        distTo[start]=0;
        //优先级队列
        Queue<State> pq = new PriorityQueue<>((a, b) -> {
            return a.distFromStart - b.distFromStart;});
        // 从起点start开始进行BFS
        pq.offer(new State(start,0));
        while (!pq.isEmpty()){
            State curState = pq.poll();
            int curNodeId=curState.id;
            int curDistFromStart=curState.distFromStart;
            if (curDistFromStart>distTo[curNodeId]){
                continue;
            }
            // 将curNodeId的相邻节点装入队列里面
            for (int[] neighbor :graph[curNodeId]){
                int nextNodeId=neighbor[0];
                int distToNextNode=distTo[curNodeId]+neighbor[1];
                //更新
                if (distTo[nextNodeId] > distToNextNode) {
                    distTo[nextNodeId] = distToNextNode;
                    pq.offer(new State(nextNodeId, distToNextNode));
                }
            }
        }
        return distTo;
    }
}

